import java.util.Hashtable;
import java.util.Iterator;
import java.util.List;
import java.util.Timer;
import java.util.TimerTask;

public class AI 
{
	//static final int TEMPS_MAX = 5000; // temps en millisecondes
	//static final int TEMPS_MARGE_MANOEUVRE = 500; // on se laisse 500 ms pour envoyer la cmd
	private static final int NB_CASES = 8;
	private static Hashtable<Character, Integer> valeurLettres = new Hashtable<Character, Integer>();
	private static Hashtable<Integer, Character> lettreChiffres = new Hashtable<Integer, Character>();
	
	private static final int directionDeplacementBlanc = 1;
	private static final int directionDeplacementNoir = -1;
	
	private static final int pousseurNoir = 2;
	private static final int pousserNoir = 1;
	private static final int pousserBlanc = 3;
	private static final int pousseurBlanc = 4;
	
	private int[][] board;
	private Node racine;
	private Node racineActuelle;
	
	private boolean joueurBlanc;
	private int directionDeplacementMax;
	private int pousseurMax;
	private int pousserMax;
	private int pousserMin;
	private int pousseurMin;
	
	//Timer timer = new Timer();	
	//boolean tempsFini;
	
	public AI()
	{		
		for(int i = 0; i < AI.NB_CASES; i++) {
			AI.valeurLettres.put((char)(65 + i), i);
			AI.lettreChiffres.put(i, (char)(65 + i));
		}
		
		this.racine = new Node(-1, -1, -1, -1);
		this.racineActuelle = this.racine;
	}
	
	public void initialiser(final int[][] board, final boolean joueurBlanc)
	{
		this.board = board;
		// Renverse le tableau virtuel pour qu'il corresponde aux coordonnees du tableau reel.
		int[][] tableauTemp = new int[AI.NB_CASES][AI.NB_CASES];
		for (int i = 0; i < AI.NB_CASES; i++) {
			for (int j = 0; j < AI.NB_CASES; j++) {
				tableauTemp[i][j] = this.board[i][(AI.NB_CASES - 1) - j];
			}
		}
		this.board = tableauTemp;
		
		this.joueurBlanc = joueurBlanc;
		if (this.joueurBlanc) {
			this.directionDeplacementMax = AI.directionDeplacementBlanc;
			this.pousseurMax = AI.pousseurBlanc;
			this.pousserMax = AI.pousserBlanc;
			this.pousserMin = AI.pousserNoir;
			this.pousseurMin = AI.pousseurNoir;
		}
		else {
			this.directionDeplacementMax = AI.directionDeplacementNoir;
			this.pousseurMax = AI.pousseurNoir;
			this.pousserMax = AI.pousserNoir;
			this.pousserMin = AI.pousserBlanc;
			this.pousseurMin = AI.pousseurBlanc;
		}
		
		this.genererDeplacementsInitiaux();
	}
	
	public String jouer(String coupAdverse)
	{
		Node deplacementAdverse = null;
		if (coupAdverse != null) {
			int departX = AI.valeurLettres.get(coupAdverse.charAt(0));
			int departY = Integer.parseInt(coupAdverse.substring(1,2)) - 1;
			int arriveeX = AI.valeurLettres.get(coupAdverse.charAt(5));
			int arriveeY = Integer.parseInt(coupAdverse.substring(6,7)) - 1;
			deplacementAdverse = new Node(departX, departY, arriveeX, arriveeY);
			this.board[arriveeX][arriveeY] = this.board[departX][departY];
			this.board[departX][departY] = 0;
			
			List<Node> vieuxDeplacements = this.racineActuelle.getEnfants();
			this.genererNouveauxDeplacements(vieuxDeplacements, deplacementAdverse, !this.joueurBlanc);
		}
		
		List<Node> deplacementsActuels = this.racineActuelle.getEnfants();
		int max = -10000;
		Node meilleurDeplacement = null;
		for (Node n : deplacementsActuels)
		{
			int valeurDeplacement = this.minimaxAlphaBeta(n, 0, this.joueurBlanc, 0, 0, 0);
			if (max < valeurDeplacement) {
				max = valeurDeplacement;
				meilleurDeplacement = n;
			}
		}
		int[] deplacement = meilleurDeplacement.getDeplacement();
		this.board[deplacement[2]][deplacement[3]] = this.board[deplacement[0]][deplacement[1]];
		this.board[deplacement[0]][deplacement[1]] = 0;
		this.genererNouveauxDeplacements(deplacementsActuels, meilleurDeplacement, this.joueurBlanc);
		
		char caseDepart = AI.lettreChiffres.get(deplacement[0]);
		char caseFin = AI.lettreChiffres.get(deplacement[2]);
		String move =  "" + caseDepart + (deplacement[1] + 1) + caseFin + (deplacement[3] + 1);
		System.out.println(move);
		return move;
	}
	
	private void genererDeplacementsInitiaux()
	{
		final Node racineNoire = new Node(-1, -1, -1, -1);
		List<Node> mouvementsBlancs = this.racine.getEnfants();
		List<Node> mouvementsNoirs = racineNoire.getEnfants();
		
		for(int y = 0; y < AI.NB_CASES; y++) {
			for(int x = 0; x < AI.NB_CASES; x++) {
				if(this.board[x][y] == AI.pousseurBlanc) {
					deplacerLigneDroite(mouvementsBlancs, true, x, y);

					deplacerDiagonaleGauche(mouvementsBlancs, true, x, y);

					deplacerDiagonaleDroite(mouvementsBlancs, true, x, y);
				}
				else if(this.board[x][y] == AI.pousseurNoir) {
					deplacerLigneDroite(mouvementsNoirs, false, x, y);

					deplacerDiagonaleGauche(mouvementsNoirs, false, x, y);

					deplacerDiagonaleDroite(mouvementsNoirs, false, x, y);
				}
			}
		}
		
		for (Node n : mouvementsBlancs) {
			n.setEnfants(mouvementsNoirs);
		}
		this.racine.setEnfants(mouvementsBlancs);
	}
	
	private void genererNouveauxDeplacements(final List<Node> deplacementsPossibles, final Node deplacement, final boolean joueurBlanc)
	{
		System.out.println("Deplacements:");
		for(Node n : deplacementsPossibles)
			System.out.println(n.getDeplacement()[0] + ", " + 
					           n.getDeplacement()[1] + " : " + 
					           n.getDeplacement()[2] + ", " +
					           n.getDeplacement()[3]);
		int[] coordonnees = deplacement.getDeplacement();
		Node nouvelleRacine = this.racineActuelle.getEnfant(deplacement);
		
		int directionDeplacement;
		int pousseurJoueur;
		int pousserJoueur;
		int pousserAdverse;
		int pousseurAdverse;
		// Joueur max
		if (this.joueurBlanc == joueurBlanc) {
			directionDeplacement = this.directionDeplacementMax;
			pousseurJoueur = this.pousseurMax;
			pousserJoueur = this.pousserMax;
			pousserAdverse = this.pousserMin;
			pousseurAdverse = this.pousseurMin;
		}
		// Joueur min
		else {
			directionDeplacement = this.directionDeplacementMax * -1;
			pousseurJoueur = this.pousseurMin;
			pousserJoueur = this.pousserMin;
			pousserAdverse = this.pousserMax;
			pousseurAdverse = this.pousseurMax;
		}
		
		// Supprime les deplacements du joueur actuel qui se debutaient a la case de debut du deplacement
		// et les deplacements du joueur actuel qui se terminaient a la case maintenant occupee.
		Iterator<Node> iterateur = deplacementsPossibles.iterator();
		while (iterateur.hasNext()) {
			Node n = iterateur.next();
			int[] deplacementPossible = n.getDeplacement();
			if ((deplacementPossible[0] == coordonnees[0] && deplacementPossible[1] == coordonnees[1])
					|| (deplacementPossible[2] == coordonnees[2] && deplacementPossible[3] == coordonnees[3])) {
				iterateur.remove();
			}
		}
		
		// Si un pousseur est bouge, ajuster les deplacements par rapport aux poussers
		if (this.board[coordonnees[2]][coordonnees[3]] == pousseurJoueur) {
			Node enfantLigneDroite;
			Node enfantDiagonaleGauche;
			Node enfantDiagonaleDroite;
			if (this.board[coordonnees[0]][coordonnees[3]] == pousserJoueur) {
				enfantLigneDroite = new Node(coordonnees[0], coordonnees[3], coordonnees[0], coordonnees[3] + directionDeplacement);
			}
			else {
				enfantLigneDroite = null;
			}
			if (coordonnees[0] != 0 && this.board[coordonnees[0] - 1][coordonnees[3]] == pousserJoueur) {
				enfantDiagonaleGauche = new Node(coordonnees[0] - 1, coordonnees[3], coordonnees[0] - 2, coordonnees[3] + directionDeplacement);
			}
			else {
				enfantDiagonaleGauche = null;
			}
			if (coordonnees[0] != 7 && this.board[coordonnees[0] + 1][coordonnees[3]] == pousserJoueur) {
				enfantDiagonaleDroite = new Node(coordonnees[0] + 1, coordonnees[3], coordonnees[0] + 2, coordonnees[3] + directionDeplacement);
			}
			else {
				enfantDiagonaleDroite = null;
			}
			
			int gaucheDroite = coordonnees[2] - coordonnees[0];
			switch (gaucheDroite) {
				case -1:
					deplacementsPossibles.remove(this.racineActuelle.getEnfant(enfantLigneDroite));
					deplacementsPossibles.remove(this.racineActuelle.getEnfant(enfantDiagonaleDroite));
					break;
				case 0:
					deplacementsPossibles.remove(this.racineActuelle.getEnfant(enfantDiagonaleGauche));
					deplacementsPossibles.remove(this.racineActuelle.getEnfant(enfantDiagonaleDroite));
					break;
				case 1:
					deplacementsPossibles.remove(this.racineActuelle.getEnfant(enfantLigneDroite));
					deplacementsPossibles.remove(this.racineActuelle.getEnfant(enfantDiagonaleGauche));
					break;
			}
			
			if (coordonnees[3] != 0 && coordonnees[3] != 7) {
				this.deplacerLigneDroite(deplacementsPossibles, joueurBlanc, coordonnees[2], coordonnees[3]);
				this.deplacerDiagonaleGauche(deplacementsPossibles, joueurBlanc, coordonnees[2], coordonnees[3]);
				this.deplacerDiagonaleDroite(deplacementsPossibles, joueurBlanc, coordonnees[2], coordonnees[3]);
			}
		}

		// Ajoute les nouveaux deplacements possibles engendres par la case nouvellement disponible.
		// Ne genere pas de nouveaux deplacements si c'est une case de fond (aucun nouveau mouvement).
		if (coordonnees[1] != 0 && coordonnees[1] != 7) {
			int caseAVerifier;

			// Deplacement en ligne droite vers la case disponible.
			caseAVerifier = this.board[coordonnees[0]][coordonnees[1] - directionDeplacement];
			// Piece qui peut faire ce deplacement est un pousseur.
			if (caseAVerifier == pousseurJoueur) {
				this.deplacerLigneDroite(deplacementsPossibles, joueurBlanc, coordonnees[0], coordonnees[1] - directionDeplacement);
			}
			// Piece qui peut faire ce deplacement est un pousser et a un pousseur a la bonne position.
			else if (caseAVerifier == pousserJoueur && 
					this.board[coordonnees[0]][coordonnees[1] - (2 * directionDeplacement)] == pousseurJoueur) {
				this.deplacerLigneDroite(deplacementsPossibles, joueurBlanc, coordonnees[0], coordonnees[1] - (2 * directionDeplacement));
			}
			
			// Deplacement en diagonale vers la gauche vers la case disponible.
			// Ne genere pas un deplacement si la case disponible est a la droite extreme du tableau.
			if (coordonnees[0] != 7) {
				caseAVerifier = this.board[coordonnees[0] + 1][coordonnees[1] - directionDeplacement];
				// Piece qui peut faire ce deplacement est un pousseur.
				if (caseAVerifier == pousseurJoueur) {
					this.deplacerDiagonaleGauche(deplacementsPossibles, joueurBlanc, coordonnees[0] + 1, coordonnees[1] - directionDeplacement);
				}
				// Piece qui peut faire ce deplacement est un pousser et a un pousseur a la bonne position.
				else if (caseAVerifier == pousserJoueur && 
						coordonnees[0] < 6 &&
						this.board[coordonnees[0] + 2][coordonnees[1] - (2 * directionDeplacement)] == pousseurJoueur) {
					this.deplacerDiagonaleGauche(deplacementsPossibles, joueurBlanc, coordonnees[0] + 2, coordonnees[1] - (2 * directionDeplacement));
				}
			}
			
			// Deplacement en diagonale vers la droite vers la case disponible.
			// Ne genere pas un deplacement si la case disponible est a la gauche extreme du tableau.
			if (coordonnees[0] != 0) {
				caseAVerifier = this.board[coordonnees[0] - 1][coordonnees[1] - directionDeplacement];
				// Piece qui peut faire ce deplacement est un pousseur.
				if (caseAVerifier == pousseurJoueur) {
					this.deplacerDiagonaleDroite(deplacementsPossibles, joueurBlanc, coordonnees[0] - 1, coordonnees[1] - directionDeplacement);
				}
				// Piece qui peut faire ce deplacement est un pousser et a un pousseur a la bonne position.
				else if (caseAVerifier == pousserJoueur && 
						coordonnees[0] > 1 &&
						this.board[coordonnees[0] - 2][coordonnees[1] - (2 * directionDeplacement)] == pousseurJoueur) {
					this.deplacerDiagonaleDroite(deplacementsPossibles, joueurBlanc, coordonnees[0] - 2, coordonnees[1] - (2* directionDeplacement));
				}
			}
		}
		
		this.racineActuelle = nouvelleRacine;
		
		List<Node> mouvementsAdversaire = this.racineActuelle.getEnfants();
		// Supprime les deplacements de l'adversaire qui utilisent la piece qui vient d'etre mangee
		boolean pieceMangee = false;
		iterateur = mouvementsAdversaire.iterator();
		while (iterateur.hasNext()) {
			Node n = iterateur.next();
			int[] deplacementPossible = n.getDeplacement();
			if (deplacementPossible[0] == coordonnees[2] && deplacementPossible[1] == coordonnees[3]) {
				iterateur.remove();
				pieceMangee = true;
			}
			// Mouvement en ligne droite bloque par piece du joueur
			else if (deplacementPossible[0] == coordonnees[2] && deplacementPossible[2] == coordonnees[2] && deplacementPossible[3] == coordonnees[3]) {
				iterateur.remove();
			}
		}

		int caseAVerifier;
		if (pieceMangee) {
			// Deplacement de l'adversaire en diagonale vers la gauche vers la case disponible.
			// Ne genere pas un deplacement si la case disponible est a la droite extreme du tableau.
			if (coordonnees[2] != 7) {
				caseAVerifier = this.board[coordonnees[2] + 1][coordonnees[3] + directionDeplacement];
				// Piece qui peut faire ce deplacement est un pousseur.
				if (caseAVerifier == pousseurAdverse) {
					this.deplacerDiagonaleGauche(mouvementsAdversaire, !joueurBlanc, coordonnees[2] + 1, coordonnees[3] + directionDeplacement);
				}
				// Piece qui peut faire ce deplacement est un pousser et a un pousseur a la bonne position.
				else if (caseAVerifier == pousserAdverse && 
						coordonnees[2] < 6 &&
						this.board[coordonnees[2] + 2][coordonnees[3] + (2 * directionDeplacement)] == pousseurAdverse) {
					this.deplacerDiagonaleGauche(mouvementsAdversaire, !joueurBlanc, coordonnees[2] + 2, coordonnees[3] + (2 * directionDeplacement));
				}
			}

			// Deplacement de l'adversaire en diagonale vers la droite vers la case disponible.
			// Ne genere pas un deplacement si la case disponible est a la gauche extreme du tableau.
			if (coordonnees[2] != 0) {
				caseAVerifier = this.board[coordonnees[2] - 1][coordonnees[3] + directionDeplacement];
				// Piece qui peut faire ce deplacement est un pousseur.
				if (caseAVerifier == pousseurAdverse) {
					this.deplacerDiagonaleDroite(mouvementsAdversaire, !joueurBlanc, coordonnees[2] - 1, coordonnees[3] + directionDeplacement);
				}
				// Piece qui peut faire ce deplacement est un pousser et a un pousseur a la bonne position.
				else if (caseAVerifier == pousserAdverse && 
						coordonnees[2] > 1 &&
						this.board[coordonnees[2] - 2][coordonnees[3] + (2 * directionDeplacement)] == pousseurAdverse) {
					this.deplacerDiagonaleDroite(mouvementsAdversaire, !joueurBlanc, coordonnees[2] - 2, coordonnees[3] + (2 * directionDeplacement));
				}
			}
		}
		
		// Deplacement de l'adversaire en ligne droite vers la case nouvellement disponible.
		caseAVerifier = this.board[coordonnees[0]][coordonnees[1] + directionDeplacement];
		// Piece qui peut faire ce deplacement est un pousseur.
		if (caseAVerifier == pousseurAdverse) {
			this.deplacerLigneDroite(mouvementsAdversaire, !joueurBlanc, coordonnees[0], coordonnees[1] + directionDeplacement);
		}
		// Piece qui peut faire ce deplacement est un pousser et a un pousseur a la bonne position.
		else if (caseAVerifier == pousserAdverse && 
				this.board[coordonnees[0]][coordonnees[1] + (2 * directionDeplacement)] == pousseurAdverse) {
			this.deplacerLigneDroite(mouvementsAdversaire, !joueurBlanc, coordonnees[0], coordonnees[1] + (2 * directionDeplacement));
		}
		
		this.racineActuelle.setEnfants(mouvementsAdversaire);
		for (Node n : this.racineActuelle.getEnfants()) {
			n.setEnfants(deplacementsPossibles);
		}
	}
	
	private void deplacerLigneDroite(final List<Node> mouvements, final boolean joueurBlanc, final int x, final int y)
	{
		int directionDeplacement;
		int pousseurJoueur;
		int pousserJoueur;
		int pousserAdversaire;
		int pousseurAdversaire;
		
		if(joueurBlanc) {
			directionDeplacement = AI.directionDeplacementBlanc;
			pousseurJoueur = AI.pousseurBlanc;
			pousserJoueur = AI.pousserBlanc;
			pousserAdversaire = AI.pousserNoir;
			pousseurAdversaire = AI.pousseurNoir;
		}
		else {
			directionDeplacement = AI.directionDeplacementNoir;
			pousseurJoueur = AI.pousseurNoir;
			pousserJoueur = AI.pousserNoir;
			pousserAdversaire = AI.pousserBlanc;
			pousseurAdversaire = AI.pousseurBlanc;
		}
			
		// La piece a bouger est un pousser.
		if(this.board[x][y + directionDeplacement] == pousserJoueur) {
			// Aucune piece occupe deja la case de destination.
			// Une piece de l'adversaire n'occupe pas la case devant la piece a bouger.
			if(!(this.board[x][y + (2 * directionDeplacement)] == pousseurJoueur || 
					this.board[x][y + (2 * directionDeplacement)] == pousserJoueur ||
					this.board[x][y + (2 * directionDeplacement)] == pousserAdversaire || 
					this.board[x][y + (2 * directionDeplacement)] == pousseurAdversaire)) {

				mouvements.add(new Node(x, y + directionDeplacement, x, y + (2 * directionDeplacement)));
			}
		}

		// La piece a bouger est un pousseur.
		else {
			// Aucune piece occupe deja la case de destination.
			if (!(this.board[x][y + directionDeplacement] == pousseurJoueur || 
					this.board[x][y + directionDeplacement] == pousserJoueur ||
					this.board[x][y + directionDeplacement] == pousserAdversaire || 
					this.board[x][y + directionDeplacement] == pousseurAdversaire)) {

				mouvements.add(new Node(x, y, x, y + directionDeplacement));
			}
		}
	}
	
	private void deplacerDiagonaleGauche(final List<Node> mouvements, final boolean joueurBlanc, final int x, final int y)
	{
		int directionDeplacement;
		int pousseurJoueur;
		int pousserJoueur;
		
		if(joueurBlanc) {
			directionDeplacement = AI.directionDeplacementBlanc;
			pousseurJoueur = AI.pousseurBlanc;
			pousserJoueur = AI.pousserBlanc;
		}
		else {
			directionDeplacement = AI.directionDeplacementNoir;
			pousseurJoueur = AI.pousseurNoir;
			pousserJoueur = AI.pousserNoir;
		}
		
		// Le pousseur n'est pas deja sur l'extreme gauche du tableau.
		if (x != 0) {
			
			// La piece a bouger est un pousser.
			if(this.board[x - 1][y + directionDeplacement] == pousserJoueur) {
				// Le pousser n'est pas deja sur l'extreme gauche du tableau et
				// aucune piece du joueur occupe deja la case de destination.
				if(x > 1 && 
						!(board[x - 2][y + (2 * directionDeplacement)] == pousseurJoueur || 
						board[x - 2][y + (2 * directionDeplacement)] == pousserJoueur)
						) {
					
					mouvements.add(new Node(x - 1, y + directionDeplacement, x - 2, y + (2 * directionDeplacement)));
				}
			}
			
			// La piece a bouger est un pousseur.
			else
			{
				// Aucune piece du joueur occupe deja la case de destination.
				if (!(board[x - 1][y + directionDeplacement] == pousseurJoueur || 
					  board[x - 1][y + directionDeplacement] == pousserJoueur)) {
					
					mouvements.add(new Node(x, y, x - 1, y + directionDeplacement));
				}
			}
		}
	}
	
	private void deplacerDiagonaleDroite(final List<Node> mouvements, final boolean joueurBlanc, final int x, final int y)
	{
		int directionDeplacement;
		int pousseurJoueur;
		int pousserJoueur;
		
		if(joueurBlanc) {
			directionDeplacement = AI.directionDeplacementBlanc;
			pousseurJoueur = AI.pousseurBlanc;
			pousserJoueur = AI.pousserBlanc;
		}
		else {
			directionDeplacement = AI.directionDeplacementNoir;
			pousseurJoueur = AI.pousseurNoir;
			pousserJoueur = AI.pousserNoir;
		}
		
		// Le pousseur n'est pas deja sur l'extreme droite du tableau.
		if(x != 7) {
			
			// La piece a bouger est un pousser.
			if(board[x + 1][y + directionDeplacement] == pousserJoueur) {
				// Le pousser n'est pas deja sur l'extreme droite du tableau et
				// aucune piece du joueur occupe deja la case de destination.
				if(x < 6 && 
						!(board[x + 2][y + (2 * directionDeplacement)] == pousseurJoueur || 
						board[x + 2][y + (2 * directionDeplacement)] == pousserJoueur)
						) {
					
					mouvements.add(new Node(x + 1, y + directionDeplacement, x + 2, y + (2 * directionDeplacement)));
				}
			}
			
			// La piece a bouger est un pousseur.
			else {
				// Aucune piece du joueur occupe deja la case de destination.
				if (!(board[x + 1][y + directionDeplacement] == pousseurJoueur ||
						board[x + 1][y + directionDeplacement] == pousserJoueur)) {
					
					mouvements.add(new Node(x, y, x + 1, y + directionDeplacement));
				}
			}
		}
	}
		
	private int evaluerDeplacement(Node deplacement)
	{
		int valeur = 0;
		
		int pousseurJoueur;
		int pousserJoueur;
		int pousserAdverse;
		int pousseurAdverse;
		
		if(this.joueurBlanc) {
			pousseurJoueur = AI.pousseurBlanc;
			pousserJoueur = AI.pousserBlanc;
			pousserAdverse = AI.pousserNoir;
			pousseurAdverse = AI.pousseurNoir;
		}
		else {
			pousseurJoueur = AI.pousseurNoir;
			pousserJoueur = AI.pousserNoir;
			pousserAdverse = AI.pousserBlanc;
			pousseurAdverse = AI.pousseurBlanc;
		}
		
		int[] coordonnees = deplacement.getDeplacement();
		int caseAVerifier = this.board[coordonnees[2]][coordonnees[3]];
		if ((coordonnees[3] == 7 && this.joueurBlanc) || (coordonnees[3] == 0 && !this.joueurBlanc)) {
			valeur = 1000;
		}
		if (caseAVerifier == pousseurAdverse) {
			valeur += 20;
		}
		else if (caseAVerifier == pousserAdverse) {
			valeur += 9;
		}
		else if (caseAVerifier == pousserJoueur) {
			valeur -= 9;
		}
		else if (caseAVerifier == pousseurJoueur) {
			valeur -= 20;
		}
		else if ((coordonnees[3] == 0 && this.joueurBlanc) || (coordonnees[3] == 7 && !this.joueurBlanc)) {
			valeur = -1000;
		}
		
		return valeur;
	}
	
	/*	void startTimer()
	{
		timer.schedule(new TimerTask() {

			public void run() {
				tempsFini = true;
			}
		}, TEMPS_MAX - TEMPS_MARGE_MANOEUVRE);
	}*/
	
	//joueur = maxplayer = true
	//joueur = minplayer = false
	private int minimaxAlphaBeta(final Node noeud, final int profondeur, final boolean joueur, int alpha, int beta, int valeur)
	{
		valeur += this.evaluerDeplacement(noeud);
		int[] deplacement = noeud.getDeplacement();
		int pieceMangee = this.board[deplacement[2]][deplacement[3]];
		this.board[deplacement[2]][deplacement[3]] = this.board[deplacement[0]][deplacement[1]];
		this.board[deplacement[0]][deplacement[1]] = 0;
		
		if (profondeur == 3 || noeud.isLeaf())
		{
			//tempsFini = false;
			this.defaireDeplacement(deplacement, pieceMangee);
			return valeur; // retourner la valeur heuristique de noeud
		}
		else {
			this.genererNouveauxDeplacements(this.racineActuelle.getEnfants(), noeud, joueur);
		}
		
		if(joueur)
		{
			for(Node child : noeud.getEnfants())
			{
				alpha = Math.max(alpha, this.minimaxAlphaBeta(child, profondeur + 1, !joueur, alpha, beta, valeur));
				
				if(beta <= alpha)
					break;
			}
		
			this.defaireDeplacement(deplacement, pieceMangee);
			return alpha;
		}
		else
		{
			for(Node child : noeud.getEnfants())
			{
				beta = Math.min(beta, this.minimaxAlphaBeta(child, profondeur + 1, !joueur, alpha, beta, valeur));
				
				if(alpha <= beta)
					break;
			}		
			
			this.defaireDeplacement(deplacement, pieceMangee);
			return beta;
		}
	}
	
	private void defaireDeplacement(final int[] deplacement, final int pieceMangee)
	{
		this.board[deplacement[0]][deplacement[1]] = this.board[deplacement[2]][deplacement[3]];
		this.board[deplacement[2]][deplacement[3]] = pieceMangee;
	}
}
